package leetcode1;
import java.util.LinkedList;
import java.util.Scanner;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 09
 * Time:19:21
 */
public class Test03 {


    /**
     * 排列组合一个字符串
     * 给一个字符串，比如ABC， 把所有的排列，即：ABC, ACB, BAC, BCA, CAB, CBC 都找出来。
     * 解题思路：
     * 对于一个n 位的字符串来讲，它是n-1位字符串的排列 加上 没有在 n -1 位字符串里 那个字符 的排列。
     * 比如：
     * 对于字符串ABC来讲，它所有的排列就是 A + BC 的排列 加上 B + AC 的排列，再加上 C + AB的排列。
     * 而BC的排列是 B + C 的排列 加上 C + B 的排列。
     * 所以，对一个字符串，我们从中去一个值，然后求剩余部分的排列，然后把它们再组合在一起。
     * @author Administrator
     *
     */

        public static void main(String[] args)
        {
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext())
            {
                LinkedList<String> list=permutation(sc.next());
                System.out.println(list);
            }
        }

        private static LinkedList<String> permutation(String str)
        {
            LinkedList<String> permuList=new LinkedList<String>();

            //递归出口，当只有字符串只包含一个字符的时候
            if(str.length()<=1)
            {
                permuList.add(str);
                return permuList;
            }

            for(int i=0;i<str.length();i++)
            {
                char ch=str.charAt(i);//当前在第一位的字符

                //相邻字符相同的情况下，会出现一样的排列组合
                //例如 "AABC"，当i=0时，当前字符'A'，子字符串为"ABC"
                //当i=1时，当前字符为'A'，子字符串为"ABC"，会得到一样的结果
                if(i>0&&ch==str.charAt(i-1))
                    continue;

                //接下来获取不包含该字符的n-1位字符构成的字符串
                String newStr=getSubString(str,i);
                //递归调用，直到newStr中只包含一个字符时
                LinkedList<String> newPermuList=permutation(newStr);
                for(int j=0;j<newPermuList.size();j++)
                {
                    permuList.add(ch+newPermuList.get(j));
                }
            }
            return permuList;
        }

        /**
         * 获取不包含当前字符的子字符串
         * 如"ABC"，当前字符为'A'，则获取字符串"BC"
         * @param str 当前字符串
         * @param i 当前字符的索引位置
         * @return
         */
        private static String getSubString(String str,int i)
        {
            //当前字符（ch）位置在str的第一位时
            if(i==0)
                return str.substring(1,str.length());
            //当前字符（ch）位置在str的最后一位时
            if(i==str.length()-1)
                return str.substring(0,str.length()-1);
            return str.substring(0,i)+str.substring(i+1,str.length());
        }


}
